#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
//This prg will rearrange inputed array and insert the no entered without change the order of this array
void bubble_rearrange (int a[], int n);
void ins ( int a[], int *n, int x);

int main()
{
    int i, n, *p, x;
    printf("How many element do you want to input? - ");
    scanf("%d", &n);
    p=malloc (n*sizeof (int));//initialize array
    
    //input each element into array
    
    for (i=0; i<n; i++)
    {
        printf("Enter the number no.%d: ", i+1);
        scanf("%d", p+i);
        }
    //Rearrange by using bubble algorithm
    bubble_rearrange (p, n);
    
    //Print out the sorted array
    printf("\nHere are your array after being sorted:\n");
    for (i=0; i<n; i++)
    {
        printf(" %d", *(p+i));
        }
    //Input the number that people want to insert to this array
    printf ("\nEnter a number that you want to insert to this array? - ");
    scanf ("%d", &x);
    
    //Do insert
    ins( p, &n, x);
    //Print out new array
    printf("\nAnd here is the new array");
    
    for (i=0; i<n; i++)
    {
        printf(" %d", *(p+i));
        }
        
    getch();
}



void bubble_rearrange (int a[], int n)
{
     int i, j, temp;
     
     for (i=n-1; i>0; i--)
     {
         for (j=0; j<i; j++)
         {
             if (*(a+j)>*(a+j+1))
             {
                     temp=*(a+j);
                     *(a+j)=*(a+j+1);
                     *(a+j+1)=temp;
                                
                                }
             }
         }
     }
     
void ins ( int a[], int *n, int x)
{
     int i, local, flag=0;
     //Find the position of number >=a[local] and mark it with flag=1
       while ((local<*n)&&!flag)
       {
   if (*(a+local)>=x)
        flag=1;//found = true
   else
	   local++;
    }
     
     
     //Move each element goto new add(add=add+1)
     if (flag)
     {
              for (i=(*n+1); i>local; i--){ *(a+i)=*(a+i-1);}
               *(a+local)=x;
              }
    
     else *(a+*n+1)=x;
     (*n)++;
}
